맨위로가기

삽입 정렬

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

삽입 정렬은 각 반복에서 입력 데이터의 요소를 정렬된 부분의 올바른 위치에 삽입하여 정렬하는 알고리즘이다. 배열을 반복하면서 정렬된 부분을 늘려나가는 방식으로 제자리에서 수행되며, 시간 복잡도는 최악의 경우 O(n2)이다. 다른 정렬 알고리즘과의 관계에서, 선택 정렬과 유사하지만 삽입 정렬은 (k+1)번째 요소가 k번째 요소보다 클 때 단일 비교만 필요하고, 이미 정렬되었거나 부분적으로 정렬된 데이터에 효율적이다. 퀵 정렬, 병합 정렬과 같은 알고리즘보다 작은 배열에서 더 빠르며, 이진 삽입 정렬, 쉘 정렬, 라이브러리 정렬 등의 개선된 변형이 존재한다. 연결 리스트로 저장된 데이터에 삽입 정렬을 적용할 수도 있다.

더 읽어볼만한 페이지

  • 온라인 정렬 - 라이브러리 정렬
    라이브러리 정렬은 정렬할 요소 사이에 간격을 두어 새로운 요소 삽입을 용이하게 하는 알고리즘으로, 이진 탐색으로 삽입 위치를 찾고 재조정 과정을 거쳐 배열 균형을 맞추며, 삽입/삭제가 잦은 동적 배열에 유용하다.
  • 안정 정렬 - 합병 정렬
    합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다.
  • 안정 정렬 - 기수 정렬
    기수 정렬은 자릿수를 기준으로 데이터를 정렬하는 비-비교 정렬 알고리즘으로, 최하위 또는 최상위 자릿수부터 시작하여 각 자릿수에 대해 안정 정렬 알고리즘을 사용하여 문자열이나 정수와 같은 데이터를 효율적으로 정렬한다.
  • 비교 정렬 - 합병 정렬
    합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다.
  • 비교 정렬 - 퀵 정렬
    퀵 정렬은 토니 호어가 개발한 분할 정복 방식의 효율적인 정렬 알고리즘으로, 피벗을 기준으로 리스트를 분할하여 정렬하는 과정을 재귀적으로 반복하며 다양한 최적화 기법과 변형이 존재한다.
삽입 정렬
개요
종류정렬 알고리즘
자료 구조배열
성능
최악 시간 복잡도O(n²) 비교 및 교환
최선 시간 복잡도O(n) 비교, O(1) 교환
평균 시간 복잡도O(n²) 비교 및 교환
공간 복잡도O(n) 전체, O(1) 보조
최적 정렬 여부아니오

2. 알고리즘

삽입 정렬은 반복을 통해 입력 요소를 하나씩 정렬된 부분에 삽입하여 최종적으로 정렬된 배열을 얻는 알고리즘이다. 각 반복에서 입력 데이터의 한 요소를 가져와 정렬된 부분에서 올바른 위치를 찾아 삽입한다. 이 과정을 입력 데이터가 모두 소진될 때까지 반복한다.

정렬은 주로 배열을 반복하면서 정렬된 부분을 늘려가는 방식으로 제자리에서 수행된다. 각 위치에서 현재 값을 정렬된 부분의 가장 큰 값과 비교한다. 만약 현재 값이 더 크면 그 자리에 두고, 작으면 정렬된 부분에서 올바른 위치를 찾아 삽입한다. 이때, 삽입 위치 이후의 값들은 한 칸씩 오른쪽으로 이동하여 공간을 만든다.

''k''번째 반복 후에는 처음 ''k'' + 1개의 항목이 정렬된 상태가 된다.

삽입 정렬의 예시
3125122211설명
31[25]122211두 번째 원소를 적절한 위치에 삽입
<25>31[12]2211세 번째 원소를 적절한 위치에 삽입
<12>2531[22]11네 번째 원소를 적절한 위치에 삽입
12<22>2531[11]마지막 원소를 적절한 위치에 삽입
<11>12222531정렬 완료



위 표는 삽입 정렬의 과정을 시각적으로 보여준다.

삽입 정렬은 다음과 같이 동작한다.

1. 첫 번째와 두 번째 요소를 비교해 순서가 맞지 않으면 교환한다.

2. 두 번째 요소부터 이전 요소들과 비교하여 작은 경우, 정렬된 위치에 삽입한다. (배열의 경우, 앞의 요소를 뒤로 하나씩 이동)

3. 세 번째 요소 이후부터는 정렬된 부분과 비교 및 삽입을 반복한다.

2. 1. 의사 코드

삽입 정렬의 그래픽 예시. 부분적으로 정렬된 목록(검정색)은 처음에 목록의 첫 번째 요소만 포함한다. 각 반복마다 하나의 요소(빨간색)가 "아직 정렬되지 않음" 입력 데이터에서 제거되어 정렬된 목록에 제자리에서 삽입된다.


배열 기반 삽입 정렬의 의사 코드는 다음과 같다. 여기서 배열은 0부터 시작한다.[2]

```

i ← 1

'''while''' i < length(A)

j ← i

'''while''' j > 0 '''and''' A[j-1] > A[j]

'''swap''' A[j] and A[j-1]

j ← j - 1

'''end while'''

i ← i + 1

'''end while'''

```

위 의사 코드에서 `'''swap'''` 연산을 `x ← A[j]; A[j] ← A[j-1]; A[j-1] ← x` (여기서 `x`는 임시 변수)로 확장하면, 다음과 같이 좀 더 빠른 버전을 만들 수 있다.[2]

```

i ← 1

'''while''' i < length(A)

x ← A[i]

j ← i

'''while''' j > 0 '''and''' A[j-1] > x

A[j] ← A[j-1]

j ← j - 1

'''end while'''

A[j] ← x[3]

i ← i + 1

'''end while'''

```

이 코드는 `A[i]` 값을 `x`에 저장하고, `x`보다 큰 값들을 오른쪽으로 이동시켜 `x`가 삽입될 위치를 확보한다.

재귀를 이용한 구현은 다음과 같다.

```

'''function''' insertionSortR(array A, int n)

'''if''' n > 0

insertionSortR(A, n-1)

x ← A[n]

j ← n-1

'''while''' j >= 0 '''and''' A[j] > x

A[j+1] ← A[j]

j ← j-1

'''end while'''

A[j+1] ← x

'''end if'''

'''end function'''

```

초기 호출은 `insertionSortR(A, length(A)-1)`이다. 이 재귀 버전은 코드를 짧게 만들거나 실행 시간을 줄이지는 않지만, 추가 메모리 소비를 O(1)에서 O(N)으로 증가시킨다.

2. 2. 동작 예시

초기 데이터1번째 루프2번째 루프3번째 루프4번째 루프5번째 루프6번째 루프7번째 루프 (정렬 완료)
84333321
48444432
33865543
77776654
66686765
55558576
22222827
11111181



삽입 정렬은 각 반복마다 입력 데이터에서 하나의 요소를 가져와 정렬된 부분에 삽입하는 방식으로 동작한다. 위 표는 이러한 과정을 숫자 배열을 통해 단계별로 보여준다. 각 단계에서 정렬된 부분은 밑줄로, 삽입될 요소는 굵게 표시된다.

3. 소스 코드

삽입 정렬은 각 반복마다 입력 요소를 하나씩 소비하며 정렬된 출력 목록을 늘리는 반복 알고리즘이다. 각 반복에서 입력 데이터의 한 요소를 제거하고, 정렬된 목록에서 해당 요소가 속할 위치를 찾아 삽입한다. 입력 요소가 모두 소진될 때까지 이 과정을 반복한다.

일반적으로 배열을 반복하여 정렬된 목록을 뒤에 늘리면서 제자리에서 정렬을 수행한다. 각 배열 위치에서 해당 위치의 값을 정렬된 목록의 가장 큰 값(이전 배열 위치에서 확인한 값)과 비교한다. 더 크면 요소를 제자리에 두고 다음으로 이동하고, 더 작으면 정렬된 목록 내에서 올바른 위치를 찾아 더 큰 값을 모두 이동시켜 공간을 만든 다음 해당 위치에 삽입한다.

''k''번 반복 후 배열은 처음 ''k'' + 1 항목이 정렬되는 속성을 가진다("+1"은 첫 번째 항목이 건너뛰어지기 때문).

x를 삽입하기 전의 배열

x를 삽입한 후의 배열

''x''와 비교할 때마다 ''x''보다 큰 각 요소는 오른쪽으로 복사된다.

배열에서 작동하는 삽입 정렬의 가장 일반적인 변형은 다음과 같이 설명할 수 있다.

# 배열 시작 부분에서 정렬된 시퀀스에 값을 삽입하도록 설계된 ''Insert'' 함수가 있다고 가정한다. 이 함수는 시퀀스 끝에서 시작하여 새 요소에 적합한 위치를 찾을 때까지 각 요소를 한 자리씩 오른쪽으로 이동하여 작동한다. 배열에서 정렬된 시퀀스 바로 뒤에 저장된 값을 덮어쓰는 부작용이 있다.

# 삽입 정렬을 수행하려면 배열의 가장 왼쪽 요소에서 시작하여 ''Insert''를 호출하여 각 요소를 올바른 위치에 삽입한다. 요소가 삽입되는 정렬된 시퀀스는 이미 검사한 인덱스 집합의 배열 시작 부분에 저장된다. 각 삽입은 단일 값, 즉 삽입되는 값을 덮어쓴다.

전체 알고리즘의 의사 코드는 다음과 같다. 여기서 배열은 0부터 시작한다.[2]

```

i ← 1

'''while''' i < length(A)

j ← i

'''while''' j > 0 '''and''' A[j-1] > A[j]

'''swap''' A[j] and A[j-1]

j ← j - 1

'''end while'''

i ← i + 1

'''end while'''

```

외부 루프는 첫 번째 요소를 제외한 모든 요소를 거친다. 단일 요소 접두사 `A[0:1]`은 사소하게 정렬되므로 처음 `i` 항목이 정렬된다는 불변량이 처음부터 참이기 때문이다. 내부 루프는 요소 `A[i]`를 올바른 위치로 이동하므로 루프 후에 처음 `i+1` 요소가 정렬된다. `'''and'''` 연산자는 단락 회로 평가를 사용해야 한다. 그렇지 않으면 `j=0`이고 `A[j-1] > A[j]` (즉, `A[-1]`에 접근)를 평가하려고 할 때 배열 범위 오류가 발생할 수 있다.

`'''swap'''` 연산을 `x ← A[j]; A[j] ← A[j-1]; A[j-1] ← x` (여기서 `x`는 임시 변수)로 확장하면, 내부 루프 본문에서 `A[i]`를 한 번에 위치로 이동하고 한 번만 할당하는 약간 더 빠른 버전을 생성할 수 있다.[2]

```

i ← 1

'''while''' i < length(A)

x ← A[i]

j ← i

'''while''' j > 0 '''and''' A[j-1] > x

A[j] ← A[j-1]

j ← j - 1

'''end while'''

A[j] ← x[3]

i ← i + 1

'''end while'''

```

새 내부 루프는 `x = A[i]`에 대한 자리를 비우기 위해 요소를 오른쪽으로 이동한다.

이 알고리즘은 재귀적인 방식으로도 구현할 수 있다. 재귀는 외부 루프를 대체하여 자체를 호출하고, ''n''이 0과 같아질 때까지 스택에 연속적으로 더 작은 값의 ''n''을 저장한다. 이 경우 함수는 ''n''이 1과 같고, 함수 인스턴스가 이전 인스턴스로 반환될 때 ''n''이 1씩 증가하는 각 재귀 호출 이후의 코드를 실행하기 위해 호출 체인을 통해 반환된다. 초기 호출은 ''insertionSortR(A, length(A)-1)''이다.

```

'''function''' insertionSortR(array A, int n)

'''if''' n > 0

insertionSortR(A, n-1)

x ← A[n]

j ← n-1

'''while''' j >= 0 '''and''' A[j] > x

A[j+1] ← A[j]

j ← j-1

'''end while'''

A[j+1] ← x

'''end if'''

'''end function'''

```

코드를 더 짧게 만들지는 않으며, 실행 시간도 줄이지 않지만 추가 메모리 소비를 증가시킨다.

항목들이 연결 리스트에 저장되어 있다면, O(1)의 추가 공간으로 리스트를 정렬할 수 있다. 알고리즘은 처음에는 비어있는(그리고 따라서 자명하게 정렬된) 리스트로 시작한다. 입력 항목들은 한 번에 하나씩 리스트에서 제거된 다음, 정렬된 리스트의 적절한 위치에 삽입된다. 입력 리스트가 비어 있으면, 정렬된 리스트는 원하는 결과를 갖는다.

아래 알고리즘은 정렬된 리스트에 삽입하기 위해 후행 포인터를 사용한다.[10] 더 간단한 재귀적 방법은 매번 리스트를 재구성하고(스플라이싱 대신) O(''n'') 스택 공간을 사용할 수 있다.

3. 1. C

다음은 C 언어로 구현된 삽입 정렬 코드이다.



void insertion_sort ( int *data, int n )

{

int i, j, remember;

for ( i = 1; i < n; i++ )

{

remember = data[(j=i)];

while ( --j >= 0 && remember < data[j] ){

data[j+1] = data[j];

}

data[j+1] = remember;

}

}



아래는 `memcpy()`를 활용하여 최적화한 C 코드이다. 정렬되는 자료가 단순 데이터일 경우에 `memcpy()`를 이용하여 자료를 밀어낼 수 있다. `memcpy()`는 자료를 당겨야 하므로 비교를 역순으로 수행한다. 위의 코드보다 25~30%가량 빠르게 처리된다.



void insertion_sort ( int *data, int n )

{

int i, j, remember;

i = n-1;

while ( i-- > 0 )

{

remember = data[(j=i)];

while ( ++j < n && remember > data[j] );

if ( --j == i ) continue;

memcpy ( data+i, data+i+1, sizeof(*data) * (j-i) );

data[j] = remember;

}

}





void

삽입_정렬(int data[], size_t n) {

for (size_t i = 1; i < n; i++) {

if (data[i - 1] > data[i]) {

size_t j = i;

int tmp = data[i];

do {

data[j] = data[j - 1];

j--;

} while (j > 0 && data[j - 1] > tmp);

data[j] = tmp;

}

}

}


3. 2. C++

cpp



#include

template

void insertion_sort(biIter begin, biIter end)

{

biIter bond = begin;

for (++bond; bond!=end; ++bond)

{

typename std::iterator_traits::value_type key = *bond;

biIter ins = bond;

biIter pre = ins;

}

}



```

수정 사항 없음:

  • 제공된 코드는 C++ 코드 스니펫이며, 위키텍스트 문법에 맞게 `` 태그로 감싸져 있습니다.
  • 별도의 템플릿이나 허용되지 않는 문법 요소가 사용되지 않았습니다.
  • 주어진 소스 코드 자체를 그대로 출력하는 것이 목적이므로, 내용 수정은 필요하지 않습니다.
  • 평어체, 한국어 사용 등 다른 지침은 코드 스니펫 외의 텍스트에 적용되는 사항입니다.

3. 3. JAVA

javascript

void insertionSort(int[] arr) {

for (int index = 1; index < arr.length; index++) {

int temp = arr[index];

int aux = index - 1;

while ((aux >= 0) && (arr[aux] > temp)) {

arr[aux + 1] = arr[aux];

aux--;

}

arr[aux + 1] = temp;

}

}

3. 4. 파이썬

python

def insert_sort(x):

for i in range(1, len(x)):

j = i - 1

key = x[i]

while x[j] > key and j >= 0:

x[j+1] = x[j]

j = j - 1

x[j+1] = key

return x

```

태그는 허용되지 않는 문법이므로 제거해야 합니다. 코드 블록은 그대로 유지하고, `python` 부분은 제거합니다.

3. 5. Objective Caml(OCaml)

ocaml

let rec isort = function

| [] -> []

| h::t -> insert h (isort t)

and insert a = function

| [] -> [a]

| h::t when a [a] @ (h::t)

| h::t -> [h] @ (insert a t);;

3. 6. Scheme

scheme

(define (insertion-sort ls)

(define (insert x ls)

(let loop ((ls ls) (acc '()))

(if (null? ls)

(append acc (cons x ls))

(let ((y (car ls)))

(if (< x y)

(append (reverse acc) (cons x ls))

(loop (cdr ls) (cons y acc)))))))

(let loop ((ls ls) (acc '()))

(if (null? ls)

acc

(let ((x (car ls)))

(loop (cdr ls) (insert x acc))))))

```

주어진 결과물은 Scheme 코드로, 위키텍스트 형식이나 기타 지침에 따른 수정이 필요하지 않습니다. 코드는 그대로 유지되어야 하며, 텍스트 서식이나 템플릿 등이 적용될 대상이 아닙니다. 따라서 원본 코드 블록을 그대로 출력합니다.

4. 복잡도

n개의 데이터가 있을 때, 최악의 경우 \sum_{i=1}^{n-1}{i} = 1+2+3+4+\cdots + (n-1) = \frac{n(n-1)}{2}번 비교하므로, 시간 복잡도는 O(n^2)이다.

삽입 정렬은 각 반복마다 입력 데이터에서 하나의 요소를 제거하고, 정렬된 목록 내에서 해당 요소가 속한 위치를 찾아 그 위치에 삽입하는 과정을 반복한다.

최선의 경우는 이미 정렬된 배열이며, 이 경우 삽입 정렬은 선형 시간(O(''n''))을 갖는다. 각 반복마다 입력의 첫 번째 남은 요소는 배열의 정렬된 부분의 가장 오른쪽 요소와만 비교하면 된다.

최악의 경우는 역순으로 정렬된 배열이다. 이 경우 내부 루프의 각 반복은 다음 요소를 삽입하기 전에 배열의 정렬된 부분 전체를 탐색하고 이동시켜야 하므로 삽입 정렬은 이차 시간(O(''n''2))을 가진다.

평균적인 경우도 이차 시간이 걸리므로,[4] 삽입 정렬은 대규모 배열 정렬에는 실용적이지 않다. 그러나 삽입 정렬은 매우 작은 배열(약 10개 정도)을 정렬하는 데 매우 빠른 알고리즘 중 하나이며, 심지어 퀵 정렬보다 빠르기도 하다.

버블 정렬과 비교하면, "교환 횟수"는 같지만, "비교 횟수"는 버블 정렬에서는 반드시 n(n-1) / 2회가 필요하지만, 삽입 정렬은 이보다 적을 수 있어 더 빠르다. 또한, 거의 정렬된 데이터에 대해서는 빠른 특징을 가지고 있다.[4]

5. 다른 정렬 알고리즘과의 관계

버블 정렬과 비교했을 때, 삽입 정렬은 일반적으로 더 적은 비교 횟수를 필요로 하여 더 빠르게 동작한다. 버블 정렬은 반드시 n(n-1) / 2회의 비교를 해야 하지만, 삽입 정렬은 그보다 적은 횟수로 정렬을 마칠 수 있다. 특히 삽입 정렬은 거의 정렬된 데이터에 대해 매우 빠른 특징을 보인다.[2]

삽입 정렬은 교환 횟수에서도 유리하다. 구현 예시에서처럼 일련의 교환 과정 중 특정 처리를 생략하여 교환 한 번에 걸리는 시간을 줄일 수 있다. 또한 데이터가 연결 리스트로 저장된 경우, 버블 정렬에 비해 큰 폭으로 속도를 향상시킬 수 있다. 배열에서는 "삽입"이 일련의 교환을 통해 구현되지만, 연결 리스트에서는 요소의 포인터만 변경하면 되므로 교환 횟수가 크게 감소하기 때문이다.[2]

5. 1. 선택 정렬

선택 정렬과 마찬가지로 배열을 ''k''번 통과하면 처음 ''k''개의 요소가 정렬된 순서가 된다. 하지만 삽입 정렬은 현재 키에서 뒤로 스캔하는 반면, 선택 정렬은 앞으로 스캔한다는 근본적인 차이점이 있다. 선택 정렬은 첫 번째 k개의 요소를 정렬되지 않은 입력에서 ''k''개의 가장 작은 요소로 만들지만, 삽입 정렬에서는 단순히 입력의 첫 번째 ''k''개 요소가 된다.[2]

삽입 정렬은 선택 정렬보다 정렬되지 않은 목록에서 절대적으로 가장 작은 요소를 찾기 위해 항상 나머지 모든 요소를 스캔할 필요가 없다는 장점이 있다. 삽입 정렬은 (''k'' + 1)-번째 요소가 ''k''번째 요소보다 클 때는 단일 비교만 필요로 한다. 입력 배열이 이미 정렬되어 있거나 부분적으로 정렬된 경우처럼 이 상황이 자주 발생하면, 삽입 정렬은 선택 정렬에 비해 훨씬 더 효율적이다. 평균적으로 삽입 정렬은 이전 ''k''개 요소의 절반을 비교하고 이동해야 하므로, 선택 정렬보다 약 절반의 비교를 수행한다.[2]

삽입 정렬의 최악의 경우(입력 배열이 역순으로 정렬된 경우)는 선택 정렬만큼 많은 비교를 수행한다. 그러나 선택 정렬보다 삽입 정렬의 단점은 각 반복에서 (''k'' + 1)-번째 요소를 배열의 정렬된 부분에 삽입하려면 다음 모든 요소를 이동하기 위해 많은 요소 교환이 필요하다는 것이다. 반면 선택 정렬의 각 반복에는 단일 교환만 필요하다. 일반적으로 삽입 정렬은 배열에 O(''n''2)번 쓰기를 수행하지만 선택 정렬은 O(n)번만 쓴다. 이러한 이유로 EEPROM 또는 플래시 메모리와 같이 메모리에 쓰는 것이 읽는 것보다 훨씬 더 비싼 경우 선택 정렬이 더 선호될 수 있다.[2]

5. 2. 퀵 정렬 및 병합 정렬

퀵 정렬 및 병합 정렬과 같은 분할 정복 알고리즘은 더 큰 배열에 대해 삽입 정렬보다 성능이 뛰어나지만, 삽입 정렬과 같은 비재귀 정렬 알고리즘은 매우 작은 배열(일반적으로 7~50개의 요소)에 대해 더 빠르다.[2] 따라서 이러한 알고리즘을 구현할 때 배열이 작은 크기로 분할되었을 경우 삽입 정렬을 사용하는 하이브리드 접근 방식이 유용하다.

6. 개선된 삽입 정렬



삽입 정렬은 각 반복마다 입력 요소를 하나씩 처리하며 정렬된 출력 목록을 늘려가는 반복 알고리즘이다. 기본적으로 입력 데이터에서 요소를 하나씩 제거하고, 정렬된 목록에서 해당 요소가 위치해야 할 곳을 찾아 삽입하는 과정을 반복한다.

일반적인 삽입 정렬은 배열을 순회하며 정렬된 부분을 늘려나가는 방식으로 작동한다. 각 위치에서 현재 값을 정렬된 부분의 값들과 비교하여, 더 작으면 올바른 위치를 찾아 삽입하고, 크면 다음 위치로 이동한다. ''k''번 반복 후에는 처음 ''k'' + 1개의 항목이 정렬된다. (이는 첫 번째 항목은 건너뛰기 때문이다.)

x를 삽입하기 전의 배열

x를 삽입한 후의 배열


  • ''x''와 비교할 때마다 ''x''보다 큰 각 요소가 오른쪽으로 복사된다.


삽입 정렬 알고리즘은 다음과 같은 의사 코드로 표현될 수 있다. (배열은 0부터 시작)[2]

```

i ← 1

'''while''' i < length(A)

x ← A[i]

j ← i

'''while''' j > 0 '''and''' A[j-1] > x

A[j] ← A[j-1]

j ← j - 1

'''end while'''

A[j] ← x[3]

i ← i + 1

'''end while'''

```

이 알고리즘은 재귀적인 방식으로도 구현할 수 있다. 재귀는 외부 루프를 대체하여 자체를 호출하고, ''n''이 0과 같아질 때까지 스택에 연속적으로 더 작은 값의 ''n''을 저장한다. 초기 호출은 ''insertionSortR(A, length(A)-1)''이다.

'''function''' insertionSortR(array A, int n)

'''if''' n > 0

insertionSortR(A, n-1)

x ← A[n]

j ← n-1

'''while''' j >= 0 '''and''' A[j] > x

A[j+1] ← A[j]

j ← j-1

'''end while'''

A[j+1] ← x

'''end if'''

'''end function'''

이 재귀적 구현은 코드를 더 짧게 만들거나 실행 시간을 줄이지는 않지만, 추가 메모리 소비를 O(1)에서 O(N)으로 증가시킨다.

삽입 정렬은 비교적 간단한 알고리즘이지만, 입력 데이터의 크기가 커질수록 비효율적이다. 이러한 단점을 극복하기 위해 다양한 개선 방법이 연구되었다. 예를 들어, 이진 병합 정렬은 이진 삽입 정렬을 사용하여 32개의 요소 그룹을 정렬한 다음 병합 정렬을 사용하여 최종 정렬을 수행하여, 소규모 데이터 집합에 대한 삽입 정렬의 속도와 대규모 데이터 집합에 대한 병합 정렬의 속도를 결합한다.[8]

6. 1. 이진 삽입 정렬

이진 삽입 정렬은 삽입 정렬의 한 종류로, 삽입할 위치를 찾을 때 이진 검색을 사용한다. 이진 검색을 사용하면 비교 횟수를 줄일 수 있어 효율적이다.[7]

일반적인 삽입 정렬은 삽입할 위치를 찾기 위해 이미 정렬된 부분을 순차적으로 탐색하지만, 이진 삽입 정렬은 이진 검색을 활용하여 탐색 시간을 단축시킨다. 이진 검색은 정렬된 배열의 중간 값과 삽입할 값을 비교하여 탐색 범위를 절반씩 줄여나가는 방식이다.

최악의 경우 이진 삽입 정렬은 ⌈log2 ''n''⌉ 번 비교를 수행한다. 하지만 각 요소를 삽입하고 배열에서 이동하는 데 평균 O(''n''2)의 시간이 걸리므로, 전체적인 시간 복잡도는 여전히 O(''n''2)이다.[7]

6. 2. 셸 정렬

D.L. 쉘이 삽입 정렬을 개선한 알고리즘으로, '셸 정렬'이라고 불린다. 셸 정렬은 각 패스마다 거리가 감소하는 요소들을 비교하여 정렬한다. 이 방식은 삽입 정렬의 비효율적인 요소 교환 문제를 개선하여 성능을 향상시킨다.[5][6] 셸 정렬은 실질적인 작업에서 실행 시간을 뚜렷하게 개선했으며, 두 가지 간단한 변형은 각각 O(''n''3/2) 및 O(''n''4/3)의 실행 시간을 갖는다.[5][6]

6. 3. 라이브러리 정렬 (갭 삽입 정렬)

라이브러리 정렬(또는 갭 삽입 정렬)은 2006년에 발표된 삽입 정렬의 한 종류이다. 이 정렬 방법은 배열 전체에 작은 수의 사용되지 않는 공간(갭)을 남겨두는 것이 특징이다. 이러한 갭 덕분에 삽입 과정에서 요소들이 갭에 도달할 때까지만 이동하면 되므로, 삽입 시간을 줄일 수 있다.[9]

이 알고리즘의 핵심 장점은 삽입 시 요소 이동을 최소화하여 효율성을 높이는 것이다. 라이브러리 정렬은 높은 확률로 시간에 실행되는 것으로 알려져 있다.[9] 이는 기존 삽입 정렬의 평균 실행 시간인 O(''n''2)에 비해 크게 개선된 결과이다.

6. 4. 연결 리스트에서의 삽입 정렬

연결 목록을 사용하면 각 삽입에 대해 일련의 스왑을 수행할 필요가 없으므로, 삽입 정렬의 효율성을 높일 수 있다. 연결 목록에서는 목록의 위치가 알려진 경우 요소를 상수 시간에 목록 안팎으로 연결할 수 있기 때문이다.

하지만 연결 목록을 검색하려면 원하는 위치까지 순차적으로 링크를 따라가야 한다. 연결 목록에는 임의 접근이 없으므로 이진 검색과 같은 더 빠른 방법을 사용할 수 없다. 따라서 검색에 필요한 실행 시간은 O(''n'')이고, 정렬에 필요한 시간은 O(''n''2)이다.

더 정교한 자료 구조 (예: 힙 또는 이진 트리)를 사용하면 검색 및 삽입에 필요한 시간을 줄일 수 있다. 이는 힙 정렬 및 이진 트리 정렬의 기반이 된다.

스킵 리스트를 사용하면 삽입 시간을 O(log ''n'')으로 줄일 수 있고, 스킵 리스트가 연결 목록 구조로 구현되므로 스왑이 필요하지 않아 삽입 정렬을 더욱 효율적으로 만들 수 있다. 삽입에 대한 최종 실행 시간은 O(''n'' log ''n'')이 된다.

연결 리스트를 사용하면 배열에서의 "삽입"과 달리, 일련의 교환 과정 없이 실제 "삽입"이 가능하므로, 버블 정렬과 비교하여 교환 횟수가 대폭 감소하여 속도 향상을 기대할 수 있다.

참조

[1] 서적 Algorithms https://archive.org/[...] Addison-Wesley
[2] 서적 Programming Pearls ACM Press / Addison-Wesley 2000
[3] 서적 Introduction to Algorithms
[4] 웹사이트 Why is insertion sort Θ(n^2) in the average case? (answer by "templatetypedef") https://stackoverflo[...] Stack Overflow
[5] 간행물 A High-Speed Sorting Procedure
[6] 간행물 A New Upper Bound for Shellsort
[7] 서적 Classic Data Structures PHI Learning
[8] 웹사이트 Binary Merge Sort https://docs.google.[...]
[9] 간행물 Insertion sort is {{nowrap|''O''(''n'' log ''n'')}}
[10] Citation Euler http://euler.vcsu.ed[...] Valley City State University 2012-09-22
[11] 웹인용 Visualising Sorting Algorithms https://upload.wikim[...] 2011-11-28


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com